1. Field of the Invention
The present invention relates to telecommunication systems, and, more particularly, to generating offset sequences for a code-division, multiple-access (CDMA) based communication schemes.
2. Description of the Related Art
Several code-division, multiple-access (CDMA) standards have been proposed, and one such standard is the IS-95 standard adopted for cellular telephony. As with many CDMA systems, IS-95 employs both a pilot channel for a base station and data, or message, channels for communication between the base station and users. Each of the base station and users communicating with the base station employ one or more assigned, pseudo-random sequences, also known as pseudo-noise (PN) sequences, for spread-spectrum xe2x80x9cspreadingxe2x80x9d of the channels. The PN sequences are used to spread, in frequency, data transmitted by the transceiver and to despread data received by the transceiver. The PN code sequence is used for both In-phase (I) and Quadrature-phase (Q) channels, is a sequence with a known number of bits, and is transmitted at a predetermined clock rate.
To determine when a signal is transmitted, and to synchronize reception and processing of a transmitted signal, the IS-95 standard specifies one or more correlation fingers, with each finger correlating a known portion of the PN code sequence with the sampled received signal. The pilot epoch is the time interval over which a PN sequence of a pilot signal repeats. The beginning of the PN sequence of the pilot channel occurs after the rollover state, which is the state at which the I-phase sequence and Q-phase sequence in respective PN generators have the same logic value in all register stages. The IS-95 system may insert an extra value in the PN sequence so that the length of the PN code sequence is an integer multiple of 2. The resulting augmented PN sequence is known in the art as a deBruijn sequence.
A (binary) PN sequence is a special form of linear shift register (LSR) sequence, so named since the sequences are generated with linear feedback of a shift register. Two popular LSR generators are Fibonacci and Galois code generators. Given a desired offset of K bits, the K-offset sequence may be generated with an LSR generator by either (i) re-initializing the state of the LSR or (ii) employing an appropriate linear combination of the state variables of the LSR. The offset K is an integer value, 1xe2x89xa6Kxe2x89xa62rxe2x88x921, where r is defined as the order of the LSR PN sequence, and is generally the length of the shift register of the LSR.
The nth binary value Pn of a PN sequence generated by an LSR generator may be defined by the following recursive formula of equation (1):                                           p            n                    =                                    ∑                              i                =                1                            r                        ⁢                          xe2x80x83                        ⁢                                          g                i                            ⁢                              p                                  n                  -                  i                                                                    ,                            (        1        )            
where the gi are generating coefficients. Addition and multiplication of equation (1) are over the (binary) Galois field (GF(2)).
The generating function of the PN sequence P(D) is defined as given in equation (2):                               P          ⁡                      (            D            )                          =                              ∑                          n              =              0                        ∞                    ⁢                      xe2x80x83                    ⁢                                    p              n                        ⁢                                          D                n                            .                                                          (        2        )            
where the value D is defined as a unit delay operator. Combining equation (1) and equation (2) provides equation (3):                                           P            ⁡                          (              D              )                                =                                    I              ⁡                              (                D                )                                                    G              ⁡                              (                D                )                                                    ,                            (        3        )            
where I(D) is the initial polynomial of the LSR sequence, the degree of which is at most rxe2x88x921, and is defined as in equation (4):                               I          ⁡                      (            D            )                          =                              ∑                          i              =              0                                      r              -              1                                ⁢                      xe2x80x83                    ⁢                                    (                                                ∑                                      j                    =                                          i                      +                      1                                                        r                                ⁢                                  xe2x80x83                                ⁢                                                      g                    j                                    ⁢                                      p                                          i                      -                      j                                                                                  )                        ⁢                          D              i                                                          (        4        )            
G(D) is referred to as the generating polynomial of the LSR sequence, and is defined as in equation (5):                               G          ⁡                      (            D            )                          =                  1          +                                    ∑                              i                =                1                            r                        ⁢                          xe2x80x83                        ⁢                                          g                i                            ⁢                              D                i                                                                        (        5        )            
Equation (4) and equation (5) show that the generating function P(D) of an LSR sequence is completely specified by its initial polynomial I(D) and the generating polynomial G(D), the generating polynomial G(D) being represented by the generating coefficients gi.
The PN sequence is periodic, with a period (number of sequence values) being the smallest integer N such that G(D) divides (1+DN) without a remainder. The zero-offset PN sequence having generating P0 (D) may be defined as p0, p1, . . . , pNxe2x88x921, p0, p1, . . . , and P0 (D)=I0(D)|G(D), with I0(D)=I(D) of equation (4).
The PN sequence offset by K bits may be a sequence as illustrated below:                                                                         p                                  N                  -                  K                                            ,                              p                                  N                  -                  K                  +                  1                                            ,              ⋯                        ⁢                          xe2x80x83                                            ⏞            K                          ⁢                  xe2x80x83                ,                  p                      N            -            1                          ,                  p          0                ,                  p          1                ,        ⋯        ⁢                  xe2x80x83                ,                  p                      N            -            K            -            1                                      ⏟        N              ,          p              N        -        K              ,    ⋯    ⁢      xe2x80x83  
For a sequence offset by K bits, the xe2x80x9cbeginningxe2x80x9d of the sequence is delayed by K bits values with respect to a reference sequence. The beginning, or zero-offset, of a periodic sequence may be arbitrarily defined within a PN sequence. For communication systems in accordance with an IS-95 standard, the reference (zero-offset) sequence is defined so that the short PN sequence starts a new cycle if the last 15 bits of the sequence from the LSR are 100000000000000 (the rollover state). For a particular implementation, additional logic may be required to insert the extra value into each sequence following 14 consecutive 1""s or 0""s. The extra value renders a 215 chip period PN sequence. Consequently, for systems such as IS-95, at the beginning of the PN sequence the value in the first register stage is forced to a logic xe2x80x9c0xe2x80x9d prior to the next state transition.
The generating function PK(D) of the PN sequence offset by K may be defined as in equation (6):                                           P            K                    ⁡                      (            D            )                          =                                                            D                K                            ⁢                                                P                  0                                ⁡                                  (                  D                  )                                                      +                                          ∑                                  i                  =                  0                                                  K                  -                  1                                            ⁢                              xe2x80x83                            ⁢                                                p                                      N                    -                    K                    +                    i                                                  ⁢                                  D                  i                                                              =                                                                      D                  K                                ⁢                                                      I                    0                                    ⁡                                      (                    D                    )                                                                              G                ⁡                                  (                  D                  )                                                      +                                          ∑                                  i                  =                  0                                                  K                  -                  1                                            ⁢                              xe2x80x83                            ⁢                                                p                                      N                    -                    K                    +                    i                                                  ⁢                                                      D                    i                                    .                                                                                        (        6        )            
PK(D) may also be defined as in equation (7):                                                         P              K                        ⁡                          (              D              )                                =                                                    I                K                            ⁡                              (                D                )                                                    G              ⁡                              (                D                )                                                    ,                            (        7        )            
From equation (6) and equation (7), IK(D) may be defined as in equation (8):
IK(D)=DKI0(D)modG(D)xe2x80x83xe2x80x83(8)
where mod (xc2x7) indicates the xe2x80x9cmodulo value of.xe2x80x9d Equation (8) shows the relation between the initial polynomials of the zero-offset and K-offset PN sequences. If I0(D) is the initial polynomial of an LSR sequence with an arbitrary offset, then IK(D) is the initial polynomial of the counterpart sequence with an offset of K bits. Therefore, the expression for I0(D) in equation (4) may given in equation (9):                                           I            0                    ⁡                      (            D            )                          =                              ∑                          i              =              0                                      r              -              1                                ⁢                      xe2x80x83                    ⁢                                    (                                                ∑                                      j                    =                                          i                      +                      1                                                        r                                ⁢                                  xe2x80x83                                ⁢                                                      g                    j                                    ⁢                                      p                                          n                      +                      i                      -                      j                                                                                  )                        ⁢                          xe2x80x83                        ⁢                          D              i                                                          (        9        )            
for some integer n.
A maximal length PN sequence with an offset of K bits from an original maximal length PN sequence is generated with a linear combination of the state variables of the LSR that relate I0(D) to IK(D). The process of employing a linear combination of the state variables is called masking. Masking is a form of 1-to-1 mapping from the LSR state at one instant to another LSR state at the same instant.
This mapping operation with masks (or masking operation) is shown in FIG. 1 for a maximal length PN sequence of 7 (2rxe2x88x921). Such PN sequence of FIG. 1 may be produced with an LSR of length 3 to yield the sequence length of 7. Each state Pi has a corresponding set of values pixe2x88x92r+1, . . . , pi, corresponding to the stages of the LSR generator shift register. For convenience, the following defines the current value of the reference PN sequence as the currently generated value pi. However, as would be apparent to one skilled in the art, some variations in the correspondence of the current value of the PN sequence and the value of the LSR stage may occur, depending upon whether the LSR generator is a Fibonacci or a Galois code generator. In addition, some variations may occur in the correspondence of the current value depending upon whether the sequence is provided from the last stage of the LSR or from the input to the first stage of the LSR.
As shown in FIG. 1, each masking operation Mij of a current state Pi of the zero-offset PN sequence provides the corresponding offset value pj of the offset sequence. As is known in the art, the masking is of the state of the LSR. Consequently, the masking operation Mij not only employs the current value pi, but also the previous values (pixe2x88x921, . . . , pixe2x88x92r+1) of the PN sequence corresponding to the current state of the LSR. As shown in FIG. 2, when an extra bit (or xe2x80x9cinsert-bitxe2x80x9d) is inserted into the original maximal length PN sequence, the mapping operation with masks may not be direct.
Referring to FIG. 3, there is shown a masking circuit 300 employed to generate an offset PN code sequence from a zero-offset sequence provided from a PN generator 308. As illustrated, PN generator 308 is a Fibonacci type LSR comprising shift register 302 having r stages, r being an integer greater than 0, r gain amplifiers 304, and a modulo-2 adder 310. The masking circuit 300 includes a mask register 312, which receives multibit mask value M=m[rxe2x88x921:0] from a mask table (not shown), combiners 314 that may be AND operators or gates, and modulo-2 adder 316. Gain amplifiers 304 have values gr, . . . , g1, which are polynomial coefficients g of the PN generating polynomial G(D). Also, the multibit value of the stages in shift register 302 is s[r: 1], and the mask value in mask register 312 is M=m[nxe2x88x921:0]. For the Fibonacci type LSR generator, the current state P of the LSR is P[rxe2x88x921:0]
Shift register 302 is initially loaded with a reference state P0, which is the initial polynomial I0(D). Then, for each clock cycle, each bit of the multibit value P[r: 1] of the shift register stages is multiplied by a corresponding one of the generating coefficients gr, . . . , g1 via gain amplifiers 304. The output values of the gain amplifiers 304 are combined in modulo-2 adder 310 to provide new value p0. This is a cyclic process. The value P0 in modulo-2 adder 310 is then applied to the first element of the shift register 302 and the last element Pr is discarded. Each value produced during the cyclic process becomes an element Pn of the zero-offset PN sequence PN[2rxe2x88x921:0]. The PN sequence may be provided as either the output of the last stage pr or the input p0 of the first stage (from modulo-2 adder 310). For each state of the shift register 302, an element may be provided of the PN sequence shifted by an offset K. Combining a state of shift register 302 with a corresponding mask value stored in mask register 312 generates this element of the K-offset sequence. Each bit of the mask value M=m[rxe2x88x921:0] is combined by combiners 314 with a corresponding one of the values P[rxe2x88x921:0:] of shift register 302. The combined mask and register stage values are then modulo-2 added by adder 316 to provide the current element of the K-offset sequence.
Since the mask values loaded into the mask register, such as that shown in FIG. 3, are themselves a sequence of states, a variation in the masking operation from an insert-bit disrupts the sequence of masks. In addition, the application of masks by the mapping operation is disrupted since several consecutive values of the PN sequence on either side of the insert-bit are used during the masking operation.
The present invention relates to generating an offset sequence from a reference sequence. The reference sequence is a PN sequence with at least one insert-bit added to form, for example, a deBruijn sequence, and the offset sequence is a cyclic-shifted reference sequence. In accordance with an exemplary embodiment of the present invention, a value of either the reference sequence or a delayed reference sequence is selected based on either the presence of an insert-bit of the reference sequence or the presence of an insert-bit of the offset sequence. A multibit mask is applied to the selected value of step and at least one previous selected value to generate a value of the offset sequence. If necessary, the at least one insert-bit is inserted into the offset sequence. The sequence of operations is repeated to generate the entire cyclic-shifted reference sequence. Generating offset sequences in accordance with the present invention may allow the masking operation to apply the sequence of masks without an interruption. Consequently, the offset deBruijn sequences of, for example, an IS-95 receiver may be generated relatively easily and may be implemented with simple hardware logic.